
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Lock Free中的Epoch Based Reclamation - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文介绍了lock free中的内存回收方法：Epoch Based Reclamation">
  <meta name="keywords" content="并行编程 内存回收 lock free epoch based reclamation">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/09/09/epochbasedreclamation/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">Lock Free中的Epoch Based Reclamation</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-09-09T22:24:02+08:00'><span class='date'><span class='date-month'>Sep</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:24 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><h2 id="section">楔子</h2>

<p>一般认为，用C/C++编写Lock Free代码非常困难，主要原因无非是两个：</p>

<blockquote>
  <ul>
    <li>内存模型</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>内存回收</li>
  </ul>
</blockquote>

<p>C++11引入了标准的内存模型，在此之前，C++程序员依赖于具体的体系结构特点和编译器提供的feature来保证正确的内存访问语义。C++11出来后，程序员编写健壮的、可移植的lock free代码成为可能。</p>

<p>但是内存回收问题依旧存在。我们知道，和Java这种提供自动gc的语言相比，C++程序员刀耕火种，得自己管理内存。当一个线程正在访问某块内存，而另外一个线程将它释放将是一个灾难行为。解决内存回收问题在lock free里显得更加困难。</p>

<p>目前用于lock free代码的内存回收的经典方法有：Lock Free Reference Counting、Hazard Pointer、Epoch Based Reclamation、Quiescent State Based Reclamation等。<a href="http://www.yebangyu.org/blog/2015/12/10/introduction-to-hazard-pointer/">上回</a>我们简单介绍了Hazard Pointer，本文我们介绍Epoch Based Reclamation方法。据我所知，这是第一篇介绍这个方法的中文资料。</p>

<!--more-->

<h2 id="section-1">概念</h2>

<p>1，逻辑删除和物理删除：逻辑删除仅仅是在逻辑上删除该节点，该节点在被逻辑删除之时可能会有其他线程正在访问它，而逻辑删除之后不会再被线程访问到。逻辑删除不回收内存空间。物理删除则是将对应的内存空间回收。一般逻辑删除对应delete，物理删除对应free或者reclaim。</p>

<p>2，Grace Period：记时间段T＝[t1,t2]，如果t1之前逻辑删除的节点，都可以在t2之后安全的回收，那么称T是一个Grace Period。t2之后保证不会有任何线程会访问在t1之前逻辑删除的节点。</p>

<p>3，临界区：在本文，临界区指的是线程访问共享内存资源的代码段。和传统上所说的临界区意义不同。</p>

<h2 id="section-2">实现</h2>

<p>我们依然先给出实现，再讲原理。注意到这里为了能focus我们的主题，我们刻意简化为四个线程，其中三个读线程，它们对数据都是只读的；而只有一个写线程可以对资源进行改写和删除，因此不需要加锁。</p>

<p>也请注意，以下伪代码只起示范作用，离真正生产环境实现还差很远。尽管如此，我们还是提供了一些实现细节和关键点(参考最后的思考一节)。</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
<span class="line-number">18</span>
<span class="line-number">19</span>
<span class="line-number">20</span>
<span class="line-number">21</span>
<span class="line-number">22</span>
<span class="line-number">23</span>
<span class="line-number">24</span>
<span class="line-number">25</span>
<span class="line-number">26</span>
<span class="line-number">27</span>
<span class="line-number">28</span>
<span class="line-number">29</span>
<span class="line-number">30</span>
<span class="line-number">31</span>
<span class="line-number">32</span>
<span class="line-number">33</span>
<span class="line-number">34</span>
<span class="line-number">35</span>
<span class="line-number">36</span>
<span class="line-number">37</span>
<span class="line-number">38</span>
<span class="line-number">39</span>
<span class="line-number">40</span>
<span class="line-number">41</span>
<span class="line-number">42</span>
<span class="line-number">43</span>
<span class="line-number">44</span>
<span class="line-number">45</span>
<span class="line-number">46</span>
<span class="line-number">47</span>
<span class="line-number">48</span>
<span class="line-number">49</span>
<span class="line-number">50</span>
<span class="line-number">51</span>
<span class="line-number">52</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="cp">#define N_THREADS 4 </span><span class="c1">//一共4个线程</span>
</span><span class="line"><span class="kt">bool</span> <span class="n">active</span><span class="p">[</span><span class="n">N_THREADS</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="nb">false</span><span class="p">};</span>
</span><span class="line"><span class="kt">int</span> <span class="n">epoches</span><span class="p">[</span><span class="n">N_THREADS</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">};</span>
</span><span class="line"><span class="kt">int</span> <span class="n">global_epoch</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
</span><span class="line"><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">*&gt;</span> <span class="n">retire_list</span><span class="p">[</span><span class="mi">3</span><span class="p">];</span>
</span><span class="line"><span class="kt">void</span> <span class="nf">read</span><span class="p">(</span><span class="kt">int</span> <span class="n">thread_id</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="n">active</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
</span><span class="line">  <span class="n">epoches</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="n">global_epoch</span><span class="p">;</span>
</span><span class="line">  <span class="c1">//进入临界区了。可以安全的读取</span>
</span><span class="line">  <span class="c1">//...... </span>
</span><span class="line">  <span class="c1">//读取完毕，离开临界区</span>
</span><span class="line">  <span class="n">active</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line"><span class="kt">void</span> <span class="nf">logical_deletion</span><span class="p">(</span><span class="kt">int</span> <span class="n">thread_id</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="n">active</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
</span><span class="line">  <span class="n">epoches</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="n">global_epoch</span><span class="p">;</span>
</span><span class="line">  <span class="c1">//进入临界区了，这里，我们可以安全的读取</span>
</span><span class="line">  <span class="c1">//好了，假如说我们现在要删除它了。先逻辑删除。</span>
</span><span class="line">  <span class="c1">//而被逻辑删除的tmp指向的节点还不能马上被回收，因此把它加入到对应的retire list</span>
</span><span class="line">  <span class="n">retire_list</span><span class="p">[</span><span class="n">global_epoch</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">tmp</span><span class="p">);</span>
</span><span class="line">  <span class="c1">//离开临界区</span>
</span><span class="line">  <span class="n">active</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
</span><span class="line">  <span class="c1">//看看能不能物理删除</span>
</span><span class="line">  <span class="n">try_gc</span><span class="p">();</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line"><span class="kt">bool</span> <span class="nf">try_gc</span><span class="p">()</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">int</span> <span class="o">&amp;</span><span class="n">e</span> <span class="o">=</span> <span class="n">global_epoch</span><span class="p">;</span>
</span><span class="line">  <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">N_THREADS</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">    <span class="k">if</span> <span class="p">(</span><span class="n">active</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">epoches</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">        <span class="c1">//还有部分线程没有更新到最新的全局的epoch值</span>
</span><span class="line">        <span class="c1">//这时候可以回收(e + 1) % 3对应的retire list。</span>
</span><span class="line">        <span class="n">free</span><span class="p">((</span><span class="n">e</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="mi">3</span><span class="p">);</span><span class="c1">//不是free(e)，也不是free(e-1)。参看下面</span>
</span><span class="line">        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="c1">//更新global epoch</span>
</span><span class="line">  <span class="n">e</span> <span class="o">=</span> <span class="p">(</span><span class="n">e</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="mi">3</span><span class="p">;</span>
</span><span class="line">  <span class="c1">//更新之后，那些active线程中，部分线程的epoch值可能还是e - 1（模3）</span>
</span><span class="line">  <span class="c1">//那些inactive的线程，之后将读到最新的值，也就是e。</span>
</span><span class="line">  <span class="c1">//不管如何，(e + 1) % 3对应的retire list的那些内存，不会有人再访问到了，可以回收它们了</span>
</span><span class="line">  <span class="c1">//因此epoch的取值需要有三种，仅仅两种是不够的。</span>
</span><span class="line">  <span class="n">free</span><span class="p">((</span><span class="n">e</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="mi">3</span><span class="p">);</span><span class="c1">//不是free(e)，也不是free(e-1)。参看下面</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line"><span class="kt">bool</span> <span class="nf">free</span><span class="p">(</span><span class="kt">int</span> <span class="n">epoch</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">for</span> <span class="n">each</span> <span class="n">pointer</span> <span class="n">in</span> <span class="n">retire_list</span><span class="p">[</span><span class="n">epoch</span><span class="p">]</span>
</span><span class="line">    <span class="k">if</span> <span class="p">(</span><span class="n">pointer</span> <span class="n">is</span> <span class="n">not</span> <span class="nb">NULL</span><span class="p">)</span>
</span><span class="line">      <span class="k">delete</span> <span class="n">pointer</span><span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

<h2 id="section-3">原理</h2>

<p>算法维护了一个全局的epoch(取值为0、1、2)和三个全局的retire_list（每个全局的epoch对应一个retire list, retire list 存放逻辑删除后待回收的节点指针）。除此之外我们为每个线程维护一个局部的active flag和epoch(取值自然也为0、1、2)。</p>

<h3 id="section-4">读线程</h3>

<p>首先设置自己的active flag 为true，表明自己需要访问共享内存。然后将自己的局部的epoch设置为全局的epoch值。</p>

<p>这之后线程就进入临界区，可以放心的读取资源了，不用担心内存会被回收。</p>

<p>离开临界区时，将自己的active flag设置为false即可。</p>

<h3 id="section-5">写线程</h3>

<p>这里说的写线程是指会对资源进行删除的线程。首先进行逻辑删除，然后尝试对它进行物理删除，也就是回收。</p>

<p>令全局的epoch值为e。首先检查，如果存在活动线程的局部epoch值不等于全局epoch值，那么可以回收retire_list[(e+1) % 3]。</p>

<p>如果不存在，那么我们把全局epoch的值更新为(e+1)%3，然后再回收对应的retire list。</p>

<p>有点绕？这里关键是理清线程局部epoch和全局epoch的关系：在这个算法里，任何时刻，全局epoch的值如果为e，那么线程的局部epoch值要么也为e，要么为e-1，不可能为e+1。</p>

<p>所以[epoch, epoch + 2]（模3）构成了一个Grace Period。</p>

<p>当全局epoch的值为1的时候，线程的局部epoch要么是1，要么是0，不可能是2。因此[2,1]构成了一个Grace Period，也就是说2对应的retire list这时候可以放心的回收了。</p>

<p>当全局epoch的值为0的时候，线程的局部epoch要么是0，要么是2，不可能是1。因此[1,0]构成了一个Grace Period，也就是说1对应的retire list这时候可以放心的回收了。</p>

<p>当全局epoch的值为2的时候，线程的局部epoch要么是2，要么是1，不可能是0。因此[0,2]构成了一个Grace Period，也就是说0对应的retire list这时候可以放心的回收了。</p>

<p>也因此，当全局epoch值为2时，如果存在部分活跃线程的局部epoch等于1，那么retire_list[1]将不能立马回收。如果这些活跃线程不退出临界区（在里面不断的读、疯狂的读，或者死了），那么retire_list[1]纪录的那些内存将一直无法回收。</p>

<p>这也就是在Epoch Based Reclamation中，回收操作可能被读延迟的原因所在。</p>

<h2 id="section-6">思考</h2>

<p>1，代码中8、9两行是写一个变量(active[i])，读另外一个变量(global_epoch)，在x86下可能会乱序，这里是否需要一个cpu级别的memory barrier？如果被乱序，有没有影响？</p>

<p>2，<code>retire_list[global_epoch].push_back(tmp);</code> 能否改为 <code>retire_list[epoches[thread_id]].push_back(tmp);</code> ？也就是说这里能否改为使用线程局部epoch值？</p>

<p>3，和Hazard Pointer相比，Epoch Based Reclamation 有什么优点和缺点？</p>

<p>4，为什么epoch有三个取值0、1、2？能不能仅使用两个？</p>

<p>5，线程局部变量我们使用了<code>active</code>数组和<code>epoches</code>数组，这里会有性能问题，为什么？提示：<a href="http://www.yebangyu.org/blog/2015/12/30/falsesharing/">False Sharing</a></p>

</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-09-09T22:24:02+08:00'><span class='date'><span class='date-month'>Sep</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:24 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/bing-xing-bian-cheng/'>并行编程</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/08/21/mcslock/" title="Previous Post: MCS Lock">&laquo; MCS Lock</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/10/13/debuggerforlockfreeprogamming/" title="Next Post: 一个轻量的lock free程序调试工具">一个轻量的lock free程序调试工具 &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
